It is known, in binary sequences or binary words of a certain length N, to correct 1-bit errors and any 2-bit errors using BCH codes by combinational error correction circuits as it is for example described in Okano, H. and Imai, H., “A construction method of high speed decoders using ROM's for Bose-Chadhuri-Hocquenghem and Reed Solomon Codes”, IEEE Trans. Comp. C36 (10) 1165-1175, 1987.
If BCH codes are used over a Galois field GF(2m), then N≦2m−1 and the error syndrome s may consist of 2m components, wherein the first m components form the sub-syndrome s1 and the second m components form the sub-syndrome s3 as it is common when using BCH codes. If the overall parity is considered, the error syndrome comprises a further binary component which is to be designated by sP.
It is further known to correct any 3-bit errors by combinational error correction circuits using BCH codes, as it is for example also described in the document by Okano, H. and Imai, H., “A construction method of high speed decoders using ROM's for Bose-Chadhuri-Hocquenghem and Reed Solomon Codes”, IEEE Trans. Comp. C36 (10) 1165-1175, 1987. When correcting any 3-bit errors, in addition to the sub-syndromes s1 and s3 a further sub-syndrome s5 may be used which like the sub-syndromes s1 and s3 that generally also comprises a word width of m bits, so that the error syndrome s=s1, s3, s5 generally comprises a word width of 3·m and taking into account the overall parity comprises a word width of 3m+1.
The correction of any 3-bit errors by combinational error correction circuits is here connected with a relatively high hardware effort and a relatively great signal runtime for the determination of the corresponding error correction signals, which may be disadvantageous. In particular, a relatively long signal runtime for the correction signals may be limiting with respect to the clock rate.
For certain circuitries it may be more likely that, when 3 bits in a binary word are erroneous, two of these erroneous bits occur in specific bit positions than that all three erroneous bits are randomly distributed.
An example for one such case may be a data storage whose memory cells may take on more than two states, in general one multivalued state each. If a data storage for example takes on 4 different states, then a memory state of a cell stores the information of two particular bits. These bits which are stored in the same memory cell are here designated as neighboring bits. Generally these bits will also be spatially adjacent in the data word to be stored. It is of course also possible to store the information of two bits which are not directly adjacent in the data word in one memory cell, like the value of the first and the seventh bits, the second and the thirteenth bits, etc. In this way of speaking, the first and the seventh bit and the second and the thirteenth bit are adjacent. In order to make the description as simple as possible, it is in the following always assumed, that neighboring bits which are for example stored in a memory cell are also spatially neighboring in the considered data word. If this is not the case, it may be acquired by a simple exchange of the bits of the data word that neighboring bits are also spatially neighboring. Thus, it is not necessary in the following to differentiate between neighboring bits which are neighboring as they are for example stored in the same memory cell and neighboring bits which are spatially neighboring or adjacent in the considered binary word.
If now an error of a memory state occurs which may e.g. take on 4 states, then two neighboring bits corresponding to this state may both be erroneous at the same time. If the assignment of the multivalued state of a memory cell to binary values is done via a Gray code, as it is common practice and for example proposed in Rupprecht, W., Steinbuch, K., “Nachrichtentechnik”, pp 339-341, Springer Verlag 1967, then errors in state values of a memory cell which only slightly change a memory state into a physically neighboring state value, lead to a 1-bit error in one of the binary values assigned with the memory state.
Errors in a memory state of a memory cell which corrupt the correct memory state into a non-neighboring memory state lead to a 2-bit error in the neighboring binary values of the binary data assigned with the memory state.
It is possible that the bits of a word which are to be corrected are auxiliary binary read values of a ternary memory or a multiple-valued memory as it is described in the U.S. patent application Ser. No. 13/664,495, filed Oct. 31, 2012 and entitled “Circuit and Method for Multi-Bit Correction” which is included here in the description by reference in its entirety.
It would be beneficial to provide an error correction of a 2-bit error in two neighboring bits (or otherwise related to each other) with relatively low hardware effort and/or relatively short signal runtime. It would also be beneficial to provide an error correction of a 2-bit error in two neighboring bits and an additional 1-bit error in an arbitrary bit position.